package com.colorsstudio.defence.algorithm
{
	import de.polygonal.ds.*;
	
	public class AStarLine
	{
		private static function compareHeuristic(left:GraphNodePointer, right:GraphNodePointer):int
		{
			//nodes with lower values are processed first
			if (left.heuristic < right.heuristic)
				return 1;
			
			if (left.heuristic > right.heuristic)
				return -1
			
			return 0;
		}
		
		public static function getPath(startNode:GraphNode, goalNode:GraphNode):LinkedStack
		{
			//trace the path by going backwards from goal node to start node
			var path:LinkedStack = new LinkedStack();
			
			var wp:Waypoint = goalNode.data;
			
			while (wp)
			{
				path.push(wp);
				wp = wp.prev;
			}
			return path;
		}
		
		public static function unmarkWaypoints(map:Graph):void
		{
			var nodes:Array = map.nodes;
			for (var i:int = 0; i < map.maxSize; i++)
			{
				var gn:GraphNode = nodes[i];
				if (gn)
				{
					var wp:Waypoint = gn.data;
					wp.init();
				}
			}
		}
		
		public static function find(map:Graph, startNode:GraphNode, goalNode:GraphNode):Boolean
		{
			unmarkWaypoints(map);
			
			//smaller heuristic values are always on top of the queue
			var queue:Heap = new Heap(1024, compareHeuristic);
			
			queue.enqueue(new GraphNodePointer(startNode, 0));
			
			var currNode:GraphNode;
			
			while (queue.size != 0)
			{
				//get the first waypoint off the queue and process it.
				var c:GraphNodePointer = queue.front;
				queue.dequeue();
				currNode = c.node;
				
				var curr_wp:Waypoint = currNode.data;
				
				//make sure the waypoint wasn't marked before,
				//because it can be enqueued multiple times
				if (!curr_wp.marked)
				{
					curr_wp.marked = true;
					
					//the goal has been reached, quit
					if (currNode == goalNode)
						return true;
					
					//loop through all nodes that are linked to the current node
					for (var i:int = 0; i < currNode.numArcs; i++)
					{
						var arc:GraphArc = currNode.arcs[i];
						var next_gn:GraphNode = arc.node;
						var next_wp:Waypoint = next_gn.data;
						
						//only process unmarked waypoints
						if (!next_wp.marked)
						{
							//calculate distance of linked waypoint: distance of current waypoint + distance to get from current to next waypoint
							var distance:Number = curr_wp.distance + curr_wp.distanceTo(next_wp) * arc.weight;
							
							//has been added to the queue before ?
							if (next_wp.prev != null)
							{
								//the node has already been calculated, check
								//if new distance is shorter
								if (distance < next_wp.distance)
								{
									next_wp.prev = curr_wp;
									next_wp.distance = distance;
								}
								//node has been processed once, and new distance is bigger, so do nothing
								else continue;
							}
							else
							{
								//first time of beeing added to the queue,
								//setup prev waypoint and distance
								next_wp.prev = curr_wp;
								next_wp.distance = distance;
							}
							
							//compute A* heuristics
							var heuristics:Number = next_wp.distanceTo(goalNode.data) + distance;
							
							//add the node to the queue
							//the heuristic value makes it happen that waypoints with the
							//smallest distance to the start waypoint are processed first
							queue.enqueue(new GraphNodePointer(next_gn, heuristics));
						}
					}
				}
			}
			return false;
		}
	}
}

import de.polygonal.ds.GraphNode;

internal class GraphNodePointer
{
	public var node:GraphNode;
	public var heuristic:Number;
	
	public function GraphNodePointer(node:GraphNode, heuristic:Number)
	{
		this.node = node;
		this.heuristic = heuristic;
	}
}